//给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的
//唯一组合。 
//
// candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
//
// 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。 
//
// 
//
// 示例 1： 
//
// 
//输入: candidates = [2,3,6,7], target = 7
//输出: [[7],[2,2,3]]
// 
//
// 示例 2： 
//
// 
//输入: candidates = [2,3,5], target = 8
//输出: [[2,2,2,2],[2,3,3],[3,5]] 
//
// 示例 3： 
//
// 
//输入: candidates = [2], target = 1
//输出: []
// 
//
// 示例 4： 
//
// 
//输入: candidates = [1], target = 1
//输出: [[1]]
// 
//
// 示例 5： 
//
// 
//输入: candidates = [1], target = 2
//输出: [[1,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= candidates.length <= 30 
// 1 <= candidates[i] <= 200 
// candidate 中的每个元素都是独一无二的。 
// 1 <= target <= 500 
// 
// Related Topics 数组 回溯 
// 👍 1648 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public static void main(String[] args) {
        Solution solution = new CombinationSum().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 稀里糊涂的就做出来了，我现在还没想明白
     * 首先对数组进行了一个排序
     * 因为值可以重复取，但是结果不能有重复的
     * 所以下次递归的起始位置是当前循环中i的位置（保证下次开始时能取到的值不比之前小）
     * 每次传入的是起始下标以及target的剩余值
     */
    class Solution {
        List<List<Integer>> res;
        List<Integer> temp;
        int[] candidates;
        int len;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            this.candidates = candidates;
            res = new ArrayList<>();
            temp = new ArrayList<>();
            len = candidates.length;
            Arrays.sort(candidates);//先进行一下排序
            dfs(target,0);
            return res;
        }

        private void dfs(int target, int begin) {
            if (target == 0){//如果目标剩余值为0说明可以添加了
                res.add(new ArrayList<>(temp));
            }else {
                for (int i = begin; i < len; i++) {
                    //如果做差之后<0了，直接进行剪枝即可，因为是排序数组了
                    if (target - candidates[i]<0) break;
                    temp.add(candidates[i]);
                    //下一个取的值只能是>=当前值
                    dfs(target-candidates[i],i);
                    temp.remove(temp.size()-1);

                }
            }
        }

        //二刷和一刷基本一样吧，candidate也事先排序了
        public void dfs(int index, int[] candidates, List<Integer> path, int target, int sum){
            if (sum == target) res.add(new ArrayList(path));
            else {
                for (int i = index; i < candidates.length; i++){
                    if (sum + candidates[i] > target) break;//这里是将数组排序后进行剪枝了
                    path.add(candidates[i]);
                    dfs(i, candidates, path, target, sum + candidates[i]);
                    path.remove(path.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}